#include <iostream>
#include <memory>
#include <list>
#include <utility>
#include <vector>
template<typename priority,typename data>
class binomialHeap;


template<typename priority,typename data>
class binomialTree{
friend class binomialHeap<priority,data>;
//private:
public:
    struct node;
public:
    binomialTree(priority p,data d){
        root = std::make_shared<node>(p,d);
        size = 0;
    }

    binomialTree(std::shared_ptr<node> r,int s){
        root = r;
        size = s;
    }

    void add(binomialTree& other){
        if (size == other.size){
            size++;
            std::shared_ptr<node> newroot,oldroot;
            if (root->Priority < other.root->Priority){
                newroot = root;
                oldroot = other.root;
            }else{
                newroot = other.root;
                oldroot = root;
            }
            (*oldroot).Sibling = (*newroot).Child;
            (*newroot).Child = oldroot;
            (*oldroot).Parent = newroot;
            root = newroot;
        }
    }

    std::pair<priority,data> minimum()const {
        return std::pair<priority,data>(root->Priority,root->Data);
    }

    int getsize(){
        return size;
    }

    void getchild(
            std::list <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >& result,
            int s){
        std::list <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > > node_list;
        std::shared_ptr<node> i = root->Child;
        s--;
        while(s >= 0){
            binomialTree<priority,data> b(i,s);
            std::shared_ptr <binomialTree<priority,data> > ptr;
            ptr = std::make_shared<binomialTree<priority,data>>(b);
            node_list.insert(node_list.begin(),std::pair<int,
                             std::shared_ptr<binomialTree<priority,data> > > (s,ptr));
            i = i->Sibling;
            s--;
        }
        result = node_list;
    }

    std::shared_ptr<struct binomialTree<priority,data>::node>
       decreasePrior(std::shared_ptr<node> ptr, priority newpriority){
       std::shared_ptr<struct binomialTree<priority,data>::node> p;
       ptr->Priority = newpriority;
       if(ptr!= root ){
            std::shared_ptr<node> parent(ptr->Parent);
            while(ptr != root && ptr->Priority < parent->Priority){
                int ptrdata = 0;
                int ptrpriority = 0;
                ptrdata = ptr->Data;
                ptrpriority = ptr->Priority;
                ptr->Data = parent->Data;
                ptr->Priority = parent->Priority;
                parent->Data = ptrdata;
                parent->Priority = ptrpriority;
                ptr = parent;
            }
        }
        return ptr;
    }
    std::list <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >
        remove(std::shared_ptr<node> ptr){
        decreasePrior(ptr,root->Priority - 1);
        std::list <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > > result;
        getchild(result,size);
        return result;
    }

//private:
public:
    struct node {
        data Data;
        priority Priority;
        std::weak_ptr<node> Parent;
        std::shared_ptr<node> Sibling;
        std::shared_ptr<node> Child;

        node(priority p,data d){
            Data = d;
            Priority = p;
            Sibling = NULL;
            Child = NULL;
        }
    };
    std::shared_ptr<node> root;
    int size;
};

template <typename priority,typename data>
class binomialHeap{
friend class binomialTree<priority,data>;
public:
    binomialHeap(binomialTree<priority,data>& b){
        std::shared_ptr<binomialTree<priority,data>> sb;
        sb = std::make_shared<binomialTree<priority,data> >(b);

        node_list.push_front(std::pair
                            <int,std::shared_ptr<binomialTree<priority,data> > >
                            (b.getsize(),sb));
    }
    binomialHeap(std::list
                 <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >& n){
        node_list = n;
    }

    binomialHeap(std::vector <std::pair <priority,data> > v){
        if (v.size() > 0){
            binomialTree<priority,data> t (v[0].first,v[0].second);
            binomialHeap h(t);
            for(int i = 1; i < v.size(); i++){
                binomialTree<priority,data> t1(v[i].first,v[i].second);
                binomialHeap<priority,data> h1(t1);
                h.add(h1);
            }
            *this = h;
        }else{
            std::cerr<<"empty vector";
            return;
        }
    }
    void add(binomialHeap& other){
        typename std::list<std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >::iterator
                fir,sec,help;
        fir = node_list.begin();
        sec = other.node_list.begin();
        std::list<std::pair<int,std::shared_ptr<binomialTree<priority,data> > > > balance;
        while (fir!= node_list.end() || sec!= other.node_list.end()){
            if(sec == other.node_list.end()){
                fir = node_list.end();
            }else
            if(fir == node_list.end()){
                node_list.push_back(*sec);
                if (sec != other.node_list.end()){
                    sec++;
                }
            }else
            {
                if (fir->first > sec->first){
                    node_list.insert(fir,*sec);
                    sec++;
                }else
                if (fir->first < sec->first){
                    fir++;
                }else
                {
                    fir->second->add(*(sec->second));
                    fir->first++;
                    fir++;
                    sec++;
                }
            }
        }
                //необходимо слить
                //больше двух одинаковых не будет
                fir = node_list.begin();
                sec=fir;
                fir++;
                //fir правее.
                while(fir != node_list.end()){
                    if (fir->first == sec->first){
                        fir->second->add(*(sec->second));
                        fir->first++;
                        node_list.erase(sec);
                        sec = fir;
                        fir++;
                    }else{
                        fir++;
                        sec++;
                    }
                }
    }

    void print(){
        std::cout<<"heap contains ";
        for (typename std::list
             <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >
             ::iterator i = node_list.begin();i!=node_list.end();i++){
            std::cout<<i->first<<" ";
        }
        std::cout<<"\n";
    }

        class nodeHandle {
        public:
            nodeHandle(std::shared_ptr<binomialTree<priority,data>> t,
                std::shared_ptr<struct binomialTree<priority,data>::node> p) {
                ptr = p;
                tptr = t;
            }

            std::shared_ptr<struct binomialTree<priority,data>::node> getptr(){
                return ptr;
            }

            std::shared_ptr<binomialTree<priority,data>> gettree(){
                return tptr;
            }

            void setptr( std::shared_ptr<struct binomialTree<priority,data>::node>& p){
                ptr = p;
            }

        private:
            std::shared_ptr<binomialTree<priority,data>> tptr;
            std::shared_ptr<struct binomialTree<priority,data>::node> ptr;
           nodeHandle(){}
        };

    nodeHandle add (priority& p,data& d){
        binomialTree<priority,data> t(p,d);
        std::shared_ptr<struct binomialTree<priority,data>::node> ptr = t.root;
        binomialHeap h(t);
        this->add(h);
        std::shared_ptr<binomialTree<priority,data>> tptr = node_list.begin()->second;
        nodeHandle n(tptr,ptr);
        return n;
    }

    data minimum(){
        data d = node_list.begin()->second->minimum().second;
        priority p = node_list.begin()->second->minimum().first;
        for (typename std::list
             <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >
             ::iterator i = node_list.begin();i!=node_list.end();i++){
            if (i->second->minimum().first < p){
                p = i->second->minimum().first;
                d = i->second->minimum().second;
            }
        }
        return d;
    }

    void extractMinimum(){
        priority p = node_list.begin()->second->minimum().second;
        typename std::list <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >
                     ::iterator del;
        for (typename std::list
             <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >
             ::iterator i = node_list.begin();i != node_list.end();i++){
            if(i->second->minimum().second<= p){
                p = i->second->minimum().second;
                del = i;
            }
        }
            std::list <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > > nodes;
            del->second->getchild(nodes,del->first);
            node_list.erase(del);
            binomialHeap n (nodes);
            if (nodes.size() > 0) {
                this->add(n);
            }
    }

    void decreasePriority(nodeHandle& n,priority p){
         std::shared_ptr<struct binomialTree<priority,data>::node> ptr
                 = n.gettree()->decreasePrior(n.getptr(),p);
         n.setptr(ptr);
    }

    void remove(nodeHandle& n){
        std::list <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > > nodes;
        nodes=n.gettree()->remove(n.getptr());
        for(typename std::list<std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >::iterator i = node_list.begin();
            i != node_list.end();i++){
            if (i->second == n.gettree()){
               typename std::list <std::pair<int,std::shared_ptr<binomialTree<priority,data> > > >::iterator j = i;
               i--;
               node_list.erase(j);
               i++;
            }
        }
        if(nodes.size() > 0){
            binomialHeap h(nodes);
            this->add(h);
        }
    }


//private:
public:
    std::list<std::pair<int,std::shared_ptr<binomialTree<priority,data> > > > node_list;
};
/*
int main()
{//придерживаемся наипрекраснейшей философии бесполезности приливаемой кучи
    binomialTree<int,int> t (3,5);
    binomialHeap<int,int> h(t);
    std::vector<std::pair<int,int>> v (10);
    v[1] = std::pair<int,int>(-5,6);
    v[8] = std::pair<int,int>(3,5);
    v[5] = std::pair<int,int>(2,2);
    v[2] = std::pair<int,int>(3,3);
    v[9] = std::pair<int,int>(6,6);
    binomialHeap<int,int> h1(v);
    std::cout<<h1.minimum();
    h1.extractMinimum();
    h1.add(h1);
    //приятно будет отследивать один добавленный элемент
    int p = 4;
    int d = 2;
    h1.add(h);
    binomialHeap<int,int>::nodeHandle n = h1.add(p,d);
    std::cout<<h1.node_list.begin()->second->root->Priority<<"\n";
    h1.decreasePriority(n,-8);
    //попробуем поддерживать ссылку при изменении приоритета
    //можно счиать, что это успех)
    std::cout<<h1.node_list.begin()->second->root->Priority<<"\n";
    h1.remove(n);
    std::cout<<h1.node_list.begin()->second->root->Priority<<"\n";
    return 0;
}
*/
